package sort.comparison;

/**
 * Created by huangyx on 2017/8/2 0002.
 */
public class Quick3way extends Base {

    //shortArrays 1
    //shortArraysR 1
    //middleArrays 43
    //middleArraysR 46
    //longArrays 587
    //longArraysR 956

    public static void sort(Comparable[] a) {
//        shuffle(a);
        sort(a, 0, a.length - 1);
    }

    public static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo)
            return;
        int lt = lo, i = lo + 1, gt = hi;
        Comparable v = a[lo];
        while (i <= gt) {
            int cmp = a[i].compareTo(v);
            if (cmp < 0)
                swap(a, lt++, i++);
            else if (cmp > 0)
                swap(a, i, gt--);
            else
                i++;
        }
        sort(a, lo, lt - 1);
        sort(a, gt + 1, hi);
    }

}
